#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time     : 2024/8/11 13:26
# @Author   : MingTai
# @File     : two_sum.py
# 两数之和
from typing import List


# Brute Force 暴力解法
# @MingTai
# N is the size of nums 数组长度为：N
# Time Complexity: O(N^2) 时间复杂度：O(N^2)
# Space Complexity: O(1) 空间复杂度 O(1)
def two_sum(nums: List[int], target: int) -> List[int]:
    result = []
    # 计算次数N
    for i in range(0, len(nums)):
        # 内部循环计算次数也是N，总共计算N^2,所以他的时间复杂度是O(N^2)
        for j in range(i + 1, len(nums)):
            total = nums[i] + nums[j]
            if total == target:
                result.append(i)
                result.append(j)
                return result


# Hash Table 哈希表解法
# @MingTai
# N is the size of nums
# Time Complexity: O(N) 时间复杂度：O(N)
# Space Complexity: O(N) 空间复杂度：O(N)
def two_sum2(nums: List[int], target: int) -> List[int]:
    result = []
    mapping = {}
    # 计算次数 N
    for i in range(0, len(nums)):
        mapping[nums[i]] = i
    for j in range(0, len(nums)):
        diff = target - nums[j]
        if diff in mapping and mapping[diff] != j:
            result.append(j)
            result.append(mapping[diff])
            return result


if __name__ == '__main__':
    aa = two_sum([1, 3, 10, 8, 13], 9)
    aa2 = two_sum2([1, 3, 10, 8, 13], 9)
    print(aa)
    print(aa2)
